{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Different Palindromic Subsequences"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countPalindromicSubsequences"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计不同回文子序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串 <code>s</code> ，返回 <code>s</code>&nbsp;中不同的非空回文子序列个数 。由于答案可能很大，请返回对 <code>10<sup>9</sup> + 7</code> <strong>取余</strong> 的结果。</p>\n",
    "\n",
    "<p>字符串的子序列可以经由字符串删除 0 个或多个字符获得。</p>\n",
    "\n",
    "<p>如果一个序列与它反转后的序列一致，那么它是回文序列。</p>\n",
    "\n",
    "<p>如果存在某个 <code>i</code> , 满足&nbsp;<code>a<sub>i</sub>&nbsp;!= b<sub>i</sub></code><sub>&nbsp;</sub>，则两个序列&nbsp;<code>a<sub>1</sub>, a<sub>2</sub>, ...</code>&nbsp;和&nbsp;<code>b<sub>1</sub>, b<sub>2</sub>, ...</code>&nbsp;不同。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = 'bccb'\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>6 个不同的非空回文子字符序列分别为：'b', 'c', 'bb', 'cc', 'bcb', 'bccb'。\n",
    "注意：'bcb' 虽然出现两次但仅计数一次。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = 'abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba'\n",
    "<strong>输出：</strong>104860361\n",
    "<strong>解释：</strong>共有 3104860382 个不同的非空回文子序列，104860361 是对 10<sup>9</sup> + 7 取余后的值。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 1000</code></li>\n",
    "\t<li><code>s[i]</code>&nbsp;仅包含&nbsp;<code>'a'</code>,&nbsp;<code>'b'</code>,&nbsp;<code>'c'</code>&nbsp;或&nbsp;<code>'d'</code>&nbsp;</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-different-palindromic-subsequences](https://leetcode.cn/problems/count-different-palindromic-subsequences/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-different-palindromic-subsequences](https://leetcode.cn/problems/count-different-palindromic-subsequences/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"bccb\"', '\"abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequences(self, s: str) -> int:\n",
    "        mod=1000000007\n",
    "        n=len(s)\n",
    "        dp=[[0]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][i]=1\n",
    "        #构建不同长度的解\n",
    "        for cur_len in range(2,n+1):\n",
    "            for i in range(0,n-cur_len+1):\n",
    "                j=i+cur_len-1\n",
    "                if s[i]!=s[j]:\n",
    "                    dp[i][j]=dp[i][j-1]+dp[i+1][j]-dp[i+1][j-1]\n",
    "                else:\n",
    "                    L=i+1\n",
    "                    R=j-1\n",
    "                    #找到第一个和s[i]相同的字符\n",
    "                    while L<=R and s[L]!=s[i]:\n",
    "                        L+=1\n",
    "                    #找到第一个和s[j]相同的字符\n",
    "                    while L<=R and s[R]!=s[i]:\n",
    "                        R-=1\n",
    "                    if L>R:\n",
    "                        dp[i][j]=2*dp[i+1][j-1]+2\n",
    "                    elif L==R:\n",
    "                        dp[i][j]=2*dp[i+1][j-1]+1\n",
    "                    else:\n",
    "                        dp[i][j]=2*dp[i+1][j-1]-dp[L+1][R-1]\n",
    "                dp[i][j]=dp[i][j]%mod\n",
    "        return dp[0][-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequences(self, s: str) -> int:\n",
    "        mod = 1000000007\n",
    "        n = len(s)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][i] = 1\n",
    "        for cur_len in range(2, n+1):\n",
    "            for i in range(0, n -cur_len+1):\n",
    "                j = i + cur_len - 1\n",
    "                if s[i] == s[j]:\n",
    "                    l, r = i + 1, j - 1\n",
    "                    while l <= r and s[l] != s[i]:\n",
    "                        l += 1\n",
    "                    while l <= r and s[r] != s[i]:\n",
    "                        r -= 1\n",
    "                    if l > r:\n",
    "                        dp[i][j] = 2 * dp[i+1][j-1] + 2\n",
    "                    elif l == r:\n",
    "                        dp[i][j] = 2 * dp[i+1][j-1] + 1\n",
    "                    else:\n",
    "                        dp[i][j] = 2 * dp[i+1][j-1] - dp[l+1][r-1]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]\n",
    "                dp[i][j] = dp[i][j] % mod\n",
    "        return dp[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequences(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        mod = 1000000007\n",
    "        last = [-1] * 256\n",
    "        left = [0] * n\n",
    "        right = [0] * n\n",
    "        for i in range(n):\n",
    "            left[i] = last[ord(s[i])]\n",
    "            last[ord(s[i])] = i\n",
    "        last = [n] * 256\n",
    "        for i in range(n-1, -1, -1):\n",
    "            right[i] = last[ord(s[i])]\n",
    "            last[ord(s[i])] = i\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][i] = 1\n",
    "        for i in range(n-2, -1, -1):\n",
    "            for j in range(i+1, n):\n",
    "                if s[i] != s[j]:\n",
    "                    dp[i][j] = dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1] + mod\n",
    "                else:\n",
    "                    l = right[i]\n",
    "                    r = left[j]\n",
    "                    if l > r:\n",
    "                        dp[i][j] = 2*dp[i+1][j-1] + 2\n",
    "                    elif l == r:\n",
    "                        dp[i][j] = 2*dp[i+1][j-1] + 1\n",
    "                    else:\n",
    "                        dp[i][j] = 2*dp[i+1][j-1] - dp[l+1][r-1] + mod\n",
    "                dp[i][j] %= mod\n",
    "        return dp[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequences(self, s: str) -> int:\n",
    "        mod = 1000000007\n",
    "        n = len(s)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][i] = 1\n",
    "\n",
    "        for cur_len in range(2, n + 1):  # 从长度为2的子串开始计算\n",
    "            # 挨个计算长度为len的子串的回文子序列个数\n",
    "            for i in range(0, n - cur_len + 1):\n",
    "                j = i + cur_len - 1\n",
    "                # 情况(1) 相等\n",
    "                if s[i] == s[j]:\n",
    "                    l, r = i + 1, j - 1\n",
    "                    while l <= r and s[l] != s[i]: l += 1\n",
    "                    while l <= r and s[r] != s[j]: r -= 1\n",
    "                    if l > r:  # 情况① 没有重复字符\n",
    "                        dp[i][j] = 2 * dp[i + 1][j - 1] + 2\n",
    "                    elif l == r:  # 情况② 出现一个重复字符\n",
    "                        dp[i][j] = 2 * dp[i + 1][j - 1] + 1\n",
    "                    else:  # 情况③ 有两个及两个以上\n",
    "                        dp[i][j] = 2 * dp[i + 1][j - 1] - dp[l + 1][r - 1]\n",
    "                else:  # 情况(2) 不相等\n",
    "                    dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1]\n",
    "                dp[i][j] = dp[i][j] % mod  # Python直接取模也没有问题\n",
    "        return dp[0][n - 1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequences(self, S: str) -> int:\n",
    "        n = len(S)\n",
    "        #M = 1e9 +7\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][i] = 1\n",
    "        for size in range(2, n + 1):\n",
    "            for i in range(n - size + 1):  # n-size +1  逆序遍历\n",
    "                j = i + size - 1\n",
    "                if S[i] != S[j]:\n",
    "                    dp[i][j] = dp[i + 1][j] + dp[i][j-1] - dp[i + 1][j - 1]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i+1][j-1] * 2  #小区间一分 外面套的大区间又有一份 所以*2\n",
    "                    l, r = i + 1, j - 1\n",
    "                    while l <= r and S[l] != S[i]: l += 1\n",
    "                    while l <= r and S[r] != S[i]: r -= 1\n",
    "                    if l > r: \n",
    "                        dp[i][j] += 2\n",
    "                    elif l == r: \n",
    "                        dp[i][j] += 1\n",
    "                    else: \n",
    "                        dp[i][j] -= dp[l + 1][r - 1]\n",
    "                    \n",
    "                dp[i][j] %= 1000000007\n",
    "        return dp[0][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequences(self, s: str) -> int:\n",
    "        # s[i] == s[j]:\n",
    "        #   dp[i][j] = dp[i + 1][j - 1] * 2 - dp[low + 1][high - 1] \n",
    "        #            = dp[i + 1][j - 1] * 2 + 1\n",
    "        #            = dp[i + 1][j - 1] * 2 + 2\n",
    "        # s[i] != s[j]:\n",
    "        #   dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1]\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(s)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        pre, nxt = [-1] * n, [n] * n\n",
    "        pre_m, nxt_m = {\"a\": -1, \"b\": -1, \"c\": -1, \"d\":-1}, {\"a\": n, \"b\": n, \"c\": n, \"d\":n}\n",
    "        for i in range(n):\n",
    "            pre[i] = pre_m[s[i]]\n",
    "            nxt[n - i - 1] = nxt_m[s[n - i -1]]\n",
    "            pre_m[s[i]] = i\n",
    "            nxt_m[s[n - i - 1]] = n - i - 1\n",
    "            dp[i][i] = 1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(i + 1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    low = nxt[i]\n",
    "                    high = pre[j]\n",
    "                    if low > high:\n",
    "                        dp[i][j] = dp[i + 1][j - 1] * 2 + 2\n",
    "                    elif low == high:\n",
    "                        dp[i][j] = dp[i + 1][j - 1] * 2 + 1\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i + 1][j - 1] * 2 - dp[low + 1][high - 1]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1]\n",
    "                dp[i][j] %= MOD\n",
    "        return dp[0][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequences(self, s: str) -> int:\n",
    "        mod = 1000000007\n",
    "        n = len(s)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        for i in range(n): dp[i][i] = 1\n",
    "\n",
    "        for cur_len in range(2, n + 1):  # 从长度为2的子串开始计算\n",
    "            # 挨个计算长度为len的子串的回文子序列个数\n",
    "            for i in range(0, n - cur_len + 1):\n",
    "                j = i + cur_len - 1\n",
    "                # 情况(1) 相等\n",
    "                if s[i] == s[j]:\n",
    "                    l, r = i + 1, j - 1\n",
    "                    while l <= r and s[l] != s[i]: l += 1\n",
    "                    while l <= r and s[r] != s[j]: r -= 1\n",
    "                    if l > r:  # 情况① 没有重复字符\n",
    "                        dp[i][j] = 2 * dp[i + 1][j - 1] + 2\n",
    "                    elif l == r:  # 情况② 出现一个重复字符\n",
    "                        dp[i][j] = 2 * dp[i + 1][j - 1] + 1\n",
    "                    else:  # 情况③ 有两个及两个以上\n",
    "                        dp[i][j] = 2 * dp[i + 1][j - 1] - dp[l + 1][r - 1]\n",
    "                else:  # 情况(2) 不相等\n",
    "                    dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1]\n",
    "                dp[i][j] = dp[i][j] % mod  # Python直接取模也没有问题\n",
    "        return dp[0][n - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequences(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        MOD = 10 ** 9 + 7\n",
    "        left, right = [-1] * n, [n] * n\n",
    "        vis = {'a': -1, 'b': -1, 'c': -1, 'd': -1}\n",
    "        for i, x in enumerate(s):\n",
    "            if vis[x] != -1:\n",
    "                left[i] = vis[x]\n",
    "            vis[x] = i\n",
    "        vis = {'a': n, 'b': n, 'c': n, 'd': n}\n",
    "        for j in range(n - 1, -1, -1):\n",
    "            if vis[s[j]] != n:\n",
    "                right[j] = vis[s[j]]\n",
    "            vis[s[j]] = j\n",
    "        for i in range(n):\n",
    "            dp[i][i] = 1\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            for j in range(i + 1, n):\n",
    "                if s[i] != s[j]:\n",
    "                    dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]\n",
    "                else:\n",
    "                    l = right[i]\n",
    "                    r = left[j]\n",
    "                    if l > r:\n",
    "                        dp[i][j] = dp[i + 1][j - 1] * 2 + 2\n",
    "                    elif l == r:\n",
    "                        dp[i][j] = dp[i + 1][j - 1] * 2 + 1\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i + 1][j - 1] * 2 - dp[l + 1][r - 1]\n",
    "                dp[i][j] %= MOD\n",
    "        return dp[0][-1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequences(self, s: str) -> int:\n",
    "        mod = 1000000007\n",
    "        n = len(s)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][i] = 1\n",
    "            if i < n-1:\n",
    "                dp[i][i+1] = 2\n",
    "\n",
    "        for cur_len in range(2, n + 1):  # 从长度为2的子串开始计算\n",
    "            # 挨个计算长度为len的子串的回文子序列个数\n",
    "            for i in range(0, n - cur_len + 1):\n",
    "                j = i + cur_len - 1\n",
    "                # 情况(1) 相等\n",
    "                if s[i] == s[j]:\n",
    "                    l, r = i + 1, j - 1\n",
    "                    while l <= r and s[l] != s[i]: l += 1\n",
    "                    while l <= r and s[r] != s[j]: r -= 1\n",
    "                    if l > r:  # 情况① 没有重复字符\n",
    "                        dp[i][j] = 2 * dp[i + 1][j - 1] + 2\n",
    "                    elif l == r:  # 情况② 出现一个重复字符\n",
    "                        dp[i][j] = 2 * dp[i + 1][j - 1] + 1\n",
    "                    else:  # 情况③ 有两个及两个以上\n",
    "                        dp[i][j] = 2 * dp[i + 1][j - 1] - dp[l + 1][r - 1]\n",
    "                else:  # 情况(2) 不相等\n",
    "                    dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1]\n",
    "                dp[i][j] = dp[i][j] % mod  # Python直接取模也没有问题\n",
    "        return dp[0][n - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequences(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        mod = 1000000007\n",
    "        last = [-1] * 256\n",
    "        left = [0] * n\n",
    "        right = [0] * n\n",
    "        for i in range(n):\n",
    "            left[i] = last[ord(s[i])]\n",
    "            last[ord(s[i])] = i\n",
    "        last = [n] * 256\n",
    "        for i in range(n-1, -1, -1):\n",
    "            right[i] = last[ord(s[i])]\n",
    "            last[ord(s[i])] = i\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][i] = 1\n",
    "        for i in range(n-2, -1, -1):\n",
    "            for j in range(i+1, n):\n",
    "                if s[i] != s[j]:\n",
    "                    dp[i][j] = dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1] + mod\n",
    "                else:\n",
    "                    l = right[i]\n",
    "                    r = left[j]\n",
    "                    if l > r:\n",
    "                        dp[i][j] = 2*dp[i+1][j-1] + 2\n",
    "                    elif l == r:\n",
    "                        dp[i][j] = 2*dp[i+1][j-1] + 1\n",
    "                    else:\n",
    "                        dp[i][j] = 2*dp[i+1][j-1] - dp[l+1][r-1]\n",
    "                dp[i][j] %= mod\n",
    "        return dp[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequences(self, s: str) -> int:\n",
    "        mod = 1000000007\n",
    "        n = len(s)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        for i in range(n): \n",
    "            dp[i][i] = 1\n",
    "            if i < n-1:\n",
    "                dp[i][i+1] = 2\n",
    "\n",
    "        for cur_len in range(2, n + 1):  # 从长度为2的子串开始计算\n",
    "            # 挨个计算长度为len的子串的回文子序列个数\n",
    "            for i in range(0, n - cur_len + 1):\n",
    "                j = i + cur_len - 1\n",
    "                # 情况(1) 相等\n",
    "                if s[i] == s[j]:\n",
    "                    l, r = i + 1, j - 1\n",
    "                    while l <= r and s[l] != s[i]: l += 1\n",
    "                    while l <= r and s[r] != s[j]: r -= 1\n",
    "                    if l > r:  # 情况① 没有重复字符\n",
    "                        dp[i][j] = 2 * dp[i + 1][j - 1] + 2\n",
    "                    elif l == r:  # 情况② 出现一个重复字符\n",
    "                        dp[i][j] = 2 * dp[i + 1][j - 1] + 1\n",
    "                    else:  # 情况③ 有两个及两个以上\n",
    "                        dp[i][j] = 2 * dp[i + 1][j - 1] - dp[l + 1][r - 1]\n",
    "                else:  # 情况(2) 不相等\n",
    "                    dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1]\n",
    "                dp[i][j] = dp[i][j] % mod  # Python直接取模也没有问题\n",
    "        return dp[0][n - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequences(self, s: str) -> int:\n",
    "        from collections import defaultdict\n",
    "        mod = 1000000007\n",
    "        prev = [None]*len(s)\n",
    "        imp = defaultdict(int)\n",
    "        for i in range(len(s)):\n",
    "            # print(i, s[i], imp[s[i]])\n",
    "            if s[i] not in imp:\n",
    "                prev[i] = -1\n",
    "                imp[s[i]] = i\n",
    "                # print(i, prev[i], s[i])\n",
    "            else:\n",
    "                prev[i] = imp[s[i]]\n",
    "                imp[s[i]] = i\n",
    "                # print(i, prev[i])\n",
    "            # print(imp)\n",
    "\n",
    "        next = [None]*len(s)\n",
    "        imp = defaultdict(int)\n",
    "        for i in range(len(s)-1, -1, -1):\n",
    "            if s[i] not in imp:\n",
    "                next[i] = len(s)\n",
    "                imp[s[i]] = i\n",
    "            else:\n",
    "                next[i] = imp[s[i]]\n",
    "                imp[s[i]] = i\n",
    "            # print(imp)\n",
    "\n",
    "        # print(prev, next)\n",
    "\n",
    "        n = len(s)\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "        \n",
    "        for l in range(n):\n",
    "            for i in range(n-l):\n",
    "                if l == 0: \n",
    "                    dp[i][i] = 1\n",
    "                else:\n",
    "                    if s[i]==s[i+l]:\n",
    "                        # print(i, i+l, s[i:i+l], next[i], prev[i+l])\n",
    "                        if next[i]>prev[i+l]:\n",
    "                            dp[i][i+l] = (2*dp[i+1][i+l-1]+2)%mod\n",
    "                            # print(1, dp[i][i+l])\n",
    "                        elif next[i]==prev[i+l]:\n",
    "                            # print(2)\n",
    "                            dp[i][i+l] = (2*dp[i+1][i+l-1]+1)%mod\n",
    "                        else:\n",
    "                            # print(3)\n",
    "                            dp[i][i+l] = (2*dp[i+1][i+l-1] - dp[next[i]+1][prev[i+l]-1])%mod\n",
    "                    else:\n",
    "                        dp[i][i+l] = (dp[i+1][i+l] + dp[i][i+l-1] - dp[i+1][i+l-1])%mod\n",
    "                # print(i, i+l, s[i:i+l+1], dp[i][i+l])\n",
    "\n",
    "        return dp[0][n-1]\n",
    "\n",
    "        # mod = 1000000007\n",
    "        # n = len(s)\n",
    "        # dp = [[0] * n for _ in range(n)]\n",
    "        # for i in range(n): dp[i][i] = 1\n",
    "\n",
    "        # for cur_len in range(2, n+1):  # 从长度为2的子串开始计算\n",
    "        #     # 挨个计算长度为len的子串的回文子序列个数\n",
    "        #     for i in range(0, n-cur_len+1):\n",
    "        #         j = i+ cur_len -1\n",
    "        #         # 情况(1) 相等\n",
    "        #         if s[i] == s[j]:\n",
    "        #             l, r = i+1, j-1\n",
    "        #             while l <= r and s[l] != s[i]: l += 1\n",
    "        #             while l <= r and s[r] != s[j]: r -= 1\n",
    "        #             if l > r:  # 情况① 没有重复字符\n",
    "        #                 dp[i][j] = 2 * dp[i+1][j-1] + 2\n",
    "        #             elif l == r:   # 情况② 出现一个重复字符\n",
    "        #                 dp[i][j] = 2 * dp[i+1][j-1] + 1\n",
    "        #             else:  # 情况③ 有两个及两个以上\n",
    "        #                 dp[i][j] = 2 * dp[i+1][j-1] - dp[l+1][r-1]\n",
    "        #         else:  # 情况(2) 不相等\n",
    "        #             dp[i][j] = dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1]\n",
    "        #         dp[i][j] = dp[i][j] % mod  # Python直接取模也没有问题\n",
    "        # return dp[0][n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequences(self, s: str) -> int:\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(s)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        next = [[0] * 4 for _ in range(n)]\n",
    "        pre = [[0] * 4 for _ in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            dp[i][i] = 1\n",
    "\n",
    "        pos = [-1] * 4\n",
    "\n",
    "        for i in range(n):\n",
    "            for c in range(4):\n",
    "                pre[i][c] = pos[c]\n",
    "            pos[ord(s[i]) - ord('a')] = i\n",
    "\n",
    "        pos[0] = pos[1] = pos[2] = pos[3] = n\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for c in range(4):\n",
    "                next[i][c] = pos[c]\n",
    "            pos[ord(s[i]) - ord('a')] = i\n",
    "\n",
    "        for sz in range(2, n + 1):\n",
    "            for j in range(sz - 1, n):\n",
    "                i = j - sz + 1\n",
    "                if s[i] == s[j]:\n",
    "                    low, high = next[i][ord(s[i]) - ord('a')], pre[j][ord(s[i]) - ord('a')]\n",
    "                    if low > high:\n",
    "                        dp[i][j] = (2 + dp[i + 1][j - 1] * 2) % MOD\n",
    "                    elif low == high:\n",
    "                        dp[i][j] = (1 + dp[i + 1][j - 1] * 2) % MOD\n",
    "                    else:\n",
    "                        dp[i][j] = (dp[i + 1][j - 1] * 2 - dp[low + 1][high - 1]) % MOD\n",
    "                else:\n",
    "                    dp[i][j] = (dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]) % MOD\n",
    "        return dp[0][n - 1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequences(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        MOD = 10 ** 9 + 7\n",
    "        left, right = [-1] * n, [n] * n\n",
    "        vis = {'a': -1, 'b': -1, 'c': -1, 'd': -1}\n",
    "        for i, x in enumerate(s):\n",
    "            if vis[x] != -1:\n",
    "                left[i] = vis[x]\n",
    "            vis[x] = i\n",
    "        vis = {'a': n, 'b': n, 'c': n, 'd': n}\n",
    "        for j in range(n - 1, -1, -1):\n",
    "            if vis[s[j]] != n:\n",
    "                right[j] = vis[s[j]]\n",
    "            vis[s[j]] = j\n",
    "        print(left, right)\n",
    "        for i in range(n):\n",
    "            dp[i][i] = 1\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            for j in range(i + 1, n):\n",
    "                if s[i] != s[j]:\n",
    "                    dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]\n",
    "                else:\n",
    "                    l = right[i]\n",
    "                    r = left[j]\n",
    "                    if l > r:\n",
    "                        dp[i][j] = dp[i + 1][j - 1] * 2 + 2\n",
    "                    elif l == r:\n",
    "                        dp[i][j] = dp[i + 1][j - 1] * 2 + 1\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i + 1][j - 1] * 2 - dp[l + 1][r - 1]\n",
    "                dp[i][j] %= MOD\n",
    "        return dp[0][-1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequences(self, s: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(s)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        next = [[0] * 4 for _ in range(n)]\n",
    "        pre = [[0] * 4 for _ in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            dp[i][i] = 1\n",
    "\n",
    "        pos = [-1] * 4\n",
    "\n",
    "        for i in range(n):\n",
    "            for c in range(4):\n",
    "                pre[i][c] = pos[c]\n",
    "            pos[ord(s[i]) - ord('a')] = i\n",
    "\n",
    "        pos[0] = pos[1] = pos[2] = pos[3] = n\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for c in range(4):\n",
    "                next[i][c] = pos[c]\n",
    "            pos[ord(s[i]) - ord('a')] = i\n",
    "\n",
    "        for sz in range(2, n + 1):\n",
    "            for j in range(sz - 1, n):\n",
    "                i = j - sz + 1\n",
    "                if s[i] == s[j]:\n",
    "                    low, high = next[i][ord(s[i]) - ord('a')], pre[j][ord(s[i]) - ord('a')]\n",
    "                    if low > high:\n",
    "                        dp[i][j] = (2 + dp[i + 1][j - 1] * 2) % MOD\n",
    "                    elif low == high:\n",
    "                        dp[i][j] = (1 + dp[i + 1][j - 1] * 2) % MOD\n",
    "                    else:\n",
    "                        dp[i][j] = (dp[i + 1][j - 1] * 2 - dp[low + 1][high - 1]) % MOD\n",
    "                else:\n",
    "                    dp[i][j] = (dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]) % MOD\n",
    "        return dp[0][n - 1]\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/count-different-palindromic-subsequences/solutions/1542287/tong-ji-bu-tong-hui-wen-zi-xu-lie-by-lee-7slg/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countPalindromicSubsequences(self, s: str) -> int:\r\n",
    "        MOD=10**9+7\r\n",
    "        L=len(s)\r\n",
    "        f=[[0]*L for _ in range(L)]\r\n",
    "        next=[[L]*4 for _ in range(L)]\r\n",
    "        prev=[[-1]*4 for _ in range(L)]\r\n",
    "        pos=[-1]*4\r\n",
    "        for i in range(L):\r\n",
    "            for c in range(4):\r\n",
    "                prev[i][c]=pos[c]\r\n",
    "            pos[ord(s[i])-ord('a')]=i\r\n",
    "\r\n",
    "        pos=[L]*4\r\n",
    "\r\n",
    "        for i in range(L-1,-1,-1):\r\n",
    "            for c in range(4):\r\n",
    "                next[i][c]=pos[c]\r\n",
    "            pos[ord(s[i])-ord('a')]=i\r\n",
    "\r\n",
    "        for i in range(L):\r\n",
    "            f[i][i]=1\r\n",
    "        \r\n",
    "        for sz in range(2,L+1):\r\n",
    "            for i in range(L-sz+1):\r\n",
    "                j=i+sz-1\r\n",
    "                if s[i]==s[j]:\r\n",
    "                    low=next[i][ord(s[i])-ord('a')]\r\n",
    "                    high=prev[j][ord(s[j])-ord('a')]\r\n",
    "                    if low>high:\r\n",
    "                        f[i][j]=2+2*f[i+1][j-1]\r\n",
    "                    elif low==high:\r\n",
    "                        f[i][j]=2*f[i+1][j-1]+1\r\n",
    "                    else:\r\n",
    "                        f[i][j]=2*f[i+1][j-1]-f[low+1][high-1]\r\n",
    "                else:\r\n",
    "                    f[i][j]=f[i+1][j]+f[i][j-1]-f[i+1][j-1]\r\n",
    "                f[i][j]%=MOD\r\n",
    "        return f[0][-1]%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequences(self, s: str) -> int:\n",
    "        N = s.__len__()\n",
    "        dp = [[0]*(N+1) for _ in range(N+1)]\n",
    "        for i in range(N):\n",
    "            dp[i][i] = 1\n",
    "        for i in reversed(range(N)):\n",
    "            for j in range(i+1, N):\n",
    "                if (ii := s.find(s[j], i, j)) == -1:\n",
    "                    dp[i][j] = dp[i][j-1]+1\n",
    "                    continue\n",
    "                if (jj := s.rfind(s[j], i, j)) == ii:\n",
    "                    dp[i][j] = dp[i][j-1]+dp[ii+1][j-1]+1\n",
    "                    continue\n",
    "                dp[i][j] = dp[i][j-1]+dp[ii+1][j-1]-dp[ii+1][jj-1]\n",
    "        return (dp[0][N-1]) % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequences(self, s: str) -> int:\n",
    "        N = s.__len__()\n",
    "        dp = [[0]*(N+1) for _ in range(N+1)]\n",
    "        for i in range(N):\n",
    "            dp[i][i] = 1\n",
    "        for i in reversed(range(N-1)):\n",
    "            for j in range(i+1, N):\n",
    "                if (ii := s.find(s[j], i, j)) == -1:\n",
    "                    dp[i][j] = dp[i][j-1]+1\n",
    "                elif (jj := s.rfind(s[j], i, j)) == ii:\n",
    "                    dp[i][j] = dp[i][j-1]+dp[ii+1][j-1]+1\n",
    "                else:\n",
    "                    dp[i][j] = dp[i][j-1]+dp[ii+1][j-1]-dp[ii+1][jj-1]\n",
    "        return (dp[0][N-1]) % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequences(self, s: str) -> int:\n",
    "        N = s.__len__()\n",
    "        dp = [[0]*(N+1) for _ in range(N+1)]\n",
    "        for i in range(N):\n",
    "            dp[i][i] = 1\n",
    "        for i in reversed(range(N)):\n",
    "            for j in range(i+1, N):\n",
    "                if (ii := s.find(s[j], i, j)) == -1:\n",
    "                    dp[i][j] = dp[i][j-1]+1\n",
    "                elif (jj := s.rfind(s[j], i, j)) == ii:\n",
    "                    dp[i][j] = dp[i][j-1]+dp[ii+1][j-1]+1\n",
    "                else:\n",
    "                    dp[i][j] = dp[i][j-1]+dp[ii+1][j-1]-dp[ii+1][jj-1]\n",
    "        return (dp[0][N-1]) % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequences(self, s: str) -> int:\n",
    "        N = s.__len__()\n",
    "        dp = [[0]*(N+1) for _ in range(N+1)]\n",
    "        for i in range(N):\n",
    "            dp[i][i] = 1\n",
    "        for i in reversed(range(N)):\n",
    "            for j in range(i+1, N):\n",
    "                if (ii := s.find(s[j], i, j)) == -1:\n",
    "                    dp[i][j] = dp[i][j-1]+1\n",
    "                    continue\n",
    "                jj = s.rfind(s[j], i, j)\n",
    "                if jj==ii:\n",
    "                    dp[i][j] = dp[i][j-1]+dp[ii+1][j-1]+1\n",
    "                    continue\n",
    "                dp[i][j] = dp[i][j-1]+dp[ii+1][j-1]-dp[ii+1][jj-1]\n",
    "        return (dp[0][N-1]) % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequences(self, s: str) -> int:\n",
    "        # def lt730(s):\n",
    "        #     chars='abcd'\n",
    "        #     c=4\n",
    "        #     n=len(s)\n",
    "        #     # dp[x][i][j] 代表字符x开头结尾的，i-j区间的，不同回文子序列的数目\n",
    "        #     dp=[[[0 for j in range(n)] for i in range(n)] for k in range(c)]\n",
    "\n",
    "        #     #因为没一个ij区间，都要用到子区间的全部x信息，所以x要放在最内层遍历；\n",
    "        #     for i in range(n-1,-1,-1):\n",
    "        #         for j in range(i,n):\n",
    "        #             for x in range(c):\n",
    "        #                 if i==j:\n",
    "        #                     if s[i]==chars[x]:dp[x][i][j]=1\n",
    "        #                 elif i<j:\n",
    "        #                     if s[i]==s[j]==chars[x]:\n",
    "        #                         dp[x][i][j]=sum([dp[x_][i+1][j-1] for x_ in range(c)  ])+2\n",
    "        #                     elif s[i]==chars[x]:\n",
    "        #                         dp[x][i][j]=dp[x][i][j-1]\n",
    "        #                     elif s[j]==chars[x]:\n",
    "        #                         dp[x][i][j]=dp[x][i+1][j]\n",
    "        #                     else:\n",
    "        #                         dp[x][i][j]=dp[x][i+1][j-1]\n",
    "        #     return sum([dp[x_][0][n-1] for x_ in range(c)])%(10**9+7)\n",
    "        # return lt730(s)\n",
    "\n",
    "        def lt730_2(s):\n",
    "            chars='abcd'\n",
    "            n=len(s)\n",
    "            pre,succ=[-1]*n,[-1]*n\n",
    "            record=[[-1]*4 for _ in range(2)]\n",
    "            for i in range(n):\n",
    "                for x in range(4):\n",
    "                    if s[i]==chars[x]:\n",
    "                        if record[0][x]==-1:\n",
    "                            record[0][x]=i\n",
    "                        else:\n",
    "                            pre[i]=record[0][x]\n",
    "                            record[0][x]=i\n",
    "                    if s[n-1-i]==chars[x]:\n",
    "                        if record[1][x]==-1:\n",
    "                            record[1][x]=n-1-i\n",
    "                        else:\n",
    "                            succ[n-1-i]=record[1][x]\n",
    "                            record[1][x]=n-1-i\n",
    "\n",
    "            dp=[[0]*n for _ in range(n)]\n",
    "            for i in range(n-1,-1,-1):\n",
    "                for j in range(i,n):\n",
    "                    if i>j:continue\n",
    "                    elif i==j:dp[i][j]=1\n",
    "                    else:\n",
    "                        if s[i]==s[j]:\n",
    "                            low,high=succ[i],pre[j]\n",
    "                            if low==-1 or high==-1 or low>=j or high<=i:\n",
    "                                dp[i][j]=2*dp[i+1][j-1]+2\n",
    "                            elif low==high:\n",
    "                                dp[i][j] = 2 * dp[i + 1][j - 1] + 1\n",
    "                            else:\n",
    "                                dp[i][j] = 2 * dp[i + 1][j - 1] -dp[low+1][high-1]\n",
    "                        else:\n",
    "                            dp[i][j]=dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1]\n",
    "            return dp[0][n-1]%(10**9+7)\n",
    "        return lt730_2(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequences(self, s: str) -> int:\n",
    "        mod_c=1000000007\n",
    "        dp=[[0]*i+[1]+[0]*(len(s)-i-1) for i in range(len(s))]\n",
    "\n",
    "        for length in range(2,len(s)+1):\n",
    "            for i in range(len(s)-length+1):\n",
    "                end=i+length-1\n",
    "                if s[i]==s[end]:\n",
    "                    l,r=i+1,end-1\n",
    "                    while l<=r and s[l]!=s[i]:\n",
    "                        l+=1\n",
    "                    while l<=r and s[r]!=s[i]:\n",
    "                        r-=1\n",
    "                    if l>r:\n",
    "                        dp[i][end]=2*dp[i+1][end-1]+2\n",
    "                    elif l==r:\n",
    "                        dp[i][end]=2*dp[i+1][end-1]+1\n",
    "                    else:\n",
    "                        dp[i][end]=2*dp[i+1][end-1]-dp[l+1][r-1]\n",
    "                else:\n",
    "                    dp[i][end]=dp[i][end-1]+dp[i+1][end]-dp[i+1][end-1]\n",
    "\n",
    "        return dp[0][len(s)-1]%mod_c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequences(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][i] = 1 \n",
    "        for l in range(2, n + 1):\n",
    "            for i in range(n - l + 1):\n",
    "                j = i + l - 1 \n",
    "                if s[i] != s[j]:\n",
    "                    dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]\n",
    "                else:\n",
    "                    dp[i][j] = 2 * dp[i + 1][j - 1] + 2\n",
    "                    lt, rt = i + 1, j - 1 \n",
    "                    while lt <= rt and s[lt] != s[i]:\n",
    "                        lt += 1 \n",
    "                    while lt <= rt and s[rt] != s[j]:\n",
    "                        rt -= 1 \n",
    "                    if lt > rt:\n",
    "                        continue \n",
    "                    elif lt == rt:\n",
    "                        dp[i][j] -= 1 \n",
    "                    else:\n",
    "                        dp[i][j] -= dp[lt + 1][rt - 1] + 1 + 1 \n",
    "        return dp[0][-1] % (10 ** 9 + 7)\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequences(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        MOD = 10 ** 9 + 7\n",
    "        # dp[x][i][j] = sum_x(dp[x][i + 1][j - 1]) + 2 if s[i] == s[j]\n",
    "        #               dp[x][i][j - 1] if s[i] == x, s[j] != x\n",
    "        #               dp[x][i + 1][j] if s[i] != x, s[j] == x\n",
    "        #               dp[x][i + 1][j - 1] if s[i] != x, s[j] != x\n",
    "        dp = [[[0] * n for _ in range(n)] for _ in range(4)]\n",
    "        for i, c in enumerate(s):\n",
    "            dp[ord(c) - 97][i][i] = 1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(i + 1, n):\n",
    "                for k in range(4):\n",
    "                    x = chr(97 + k)\n",
    "                    if s[i] == x and s[j] == x:\n",
    "                        for t in range(4):\n",
    "                            dp[k][i][j] += dp[t][i + 1][j - 1]\n",
    "                            dp[k][i][j] %= MOD\n",
    "                        dp[k][i][j] += 2\n",
    "                        dp[k][i][j] %= MOD\n",
    "                    elif s[i] == x:\n",
    "                        dp[k][i][j] = dp[k][i][j - 1]\n",
    "                    elif s[j] == x:\n",
    "                        dp[k][i][j] = dp[k][i + 1][j]\n",
    "                    else:\n",
    "                        dp[k][i][j] = dp[k][i + 1][j - 1]\n",
    "            \n",
    "        ans = 0\n",
    "        for t in range(4):\n",
    "            ans += dp[t][0][n - 1]\n",
    "            ans %= MOD\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countPalindromicSubsequences(self, s: str) -> int:\r\n",
    "        MOD=10**9+7\r\n",
    "        L=len(s)\r\n",
    "        f=[[[0]*L for _ in range(L)] for _ in range(4)]\r\n",
    "        for i,c in enumerate(s):\r\n",
    "            f[ord(c)-ord('a')][i][i]=1\r\n",
    "        \r\n",
    "        for sz in range(2,L+1):\r\n",
    "            for i in range(L-sz+1):\r\n",
    "                j=i+sz-1\r\n",
    "            # for j in range(sz-1,L):\r\n",
    "            #     i=j-sz+1\r\n",
    "                for k,c in enumerate('abcd'):\r\n",
    "                    if s[i]==c and s[j]==c:\r\n",
    "                        f[k][i][j]=(2+sum(d[i+1][j-1] for d in f))%MOD\r\n",
    "                    elif s[i]==c:\r\n",
    "                        f[k][i][j]=f[k][i][j-1]\r\n",
    "                    elif s[j]==c:\r\n",
    "                        f[k][i][j]=f[k][i+1][j]\r\n",
    "                    else:\r\n",
    "                        f[k][i][j]=f[k][i+1][j-1]\r\n",
    "        return sum(d[0][-1] for d in f)%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequences(self, s: str) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        n = len(s)\n",
    "        dp = [[[0] * n for _ in range(n)] for _ in range(4)]\n",
    "        for i, c in enumerate(s):\n",
    "            dp[ord(c) - ord(\"a\")][i][i] = 1\n",
    "        for sz in range(2, n + 1):\n",
    "            for j in range(sz - 1, n):\n",
    "                i = j - sz + 1\n",
    "                for k, c in enumerate(\"abcd\"):\n",
    "                    if s[i] == c and s[j] == c:\n",
    "                        dp[k][i][j] = (2 + sum(d[i + 1][j - 1] for d in dp)) % MOD\n",
    "                    elif s[i] == c:\n",
    "                        dp[k][i][j] = dp[k][i][j - 1]\n",
    "                    elif s[j] == c:\n",
    "                        dp[k][i][j] = dp[k][i + 1][j]\n",
    "                    else:\n",
    "                        dp[k][i][j] = dp[k][i + 1][j - 1]\n",
    "        return sum(d[0][n - 1] for d in dp) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequences(self, s: str) -> int:\n",
    "        # dp(x,i,j) 表示在s[i~j]中以字符 x 为开头和结尾的不同回文序列总数\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(s)\n",
    "        dp = [[[0] * n for _ in range(n)] for _ in range(4)]\n",
    "        for i, c in enumerate(s):\n",
    "            dp[ord(c) - ord('a')][i][i] = 1\n",
    "\n",
    "        for L in range(2, n + 1):\n",
    "            for j in range(L - 1, n):\n",
    "                i = j - L + 1\n",
    "                for k, c in enumerate(\"abcd\"):\n",
    "                    if s[i] == c and s[j] == c:\n",
    "                        # +2的意思是：cc和c\n",
    "                        # i != j, 所以单独一个c不会和初始化重复\n",
    "                        dp[k][i][j] = (2 + sum(d[i + 1][j - 1] for d in dp)) % MOD\n",
    "                    elif s[i] == c:\n",
    "                        dp[k][i][j] = dp[k][i][j - 1]\n",
    "                    elif s[j] == c:\n",
    "                        dp[k][i][j] = dp[k][i + 1][j]\n",
    "                    else:\n",
    "                        dp[k][i][j] = dp[k][i + 1][j - 1]\n",
    "        return sum(d[0][n - 1] for d in dp) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#统计不同回文子序列,记忆化搜索\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def countPalindromicSubsequences(self, s: str) -> int:\n",
    "        # mod=10**9+7\n",
    "        # @lru_cache(None)\n",
    "        # def dfs(left,right):\n",
    "        #     if left>=right:return int(left==right)#如果l==r,搜索到单字符，对结果贡献为1\n",
    "        #     res=0\n",
    "        #     for ch in'abcd':\n",
    "        #         l,r=s.find(ch,left,right+1),s.rfind(ch,left,right+1)\n",
    "        #         if l==-1:continue \n",
    "        #         if r==l:res+=1\n",
    "        #         else:res+=dfs(l+1,r-1)+2\n",
    "        #         res%=mod\n",
    "        #     return res \n",
    "        # return dfs(0,len(s)-1)\n",
    "        #dp\n",
    "        mod=10**9+7\n",
    "        n=len(s)\n",
    "        #状态 dp(x,i,j) 表示在字符串区间 s[i:j]中以字符 xxx 为开头和结尾的不同「回文序列」总数，其中 s[i:j]表示字符串s从下标 i到下标 j的子串（包含下标 i 和下标j）\n",
    "        dp=[[[0]*n for i in range(n)] for j in range(4)]#三维dp，dp[k][i][j],\n",
    "        for i,c in enumerate(s):\n",
    "            dp[ord(c)-ord('a')][i][i]=1\n",
    "        for sz in range(2,n+1):\n",
    "            for j in range(sz-1,n):\n",
    "                i=j-sz+1\n",
    "                for k,c in enumerate('abcd'):\n",
    "                    if s[i]==c and s[j]==c:\n",
    "                        dp[k][i][j]=(2+sum(d[i+1][j-1] for d in dp))%mod \n",
    "                    elif s[i]==c:\n",
    "                        dp[k][i][j]=dp[k][i][j-1]\n",
    "                    elif s[j]==c:\n",
    "                        dp[k][i][j]=dp[k][i+1][j]\n",
    "                    else:\n",
    "                        dp[k][i][j]=dp[k][i+1][j-1]\n",
    "        return sum(d[0][n-1]for d in dp)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequences(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[[0]*n for _ in range(n)] for _ in range(4)]\n",
    "        char_list = ['a', 'b', 'c', 'd'] \n",
    "        for k in range(4):\n",
    "            ch = char_list[k]\n",
    "            for i in range(n):\n",
    "                dp[k][i][i] = int(s[i]==ch)\n",
    "        \n",
    "        for L in range(2, n+1):\n",
    "            for i in range(n-L+1):\n",
    "                j = L+i-1\n",
    "                for k in range(4):\n",
    "                    if s[i] == s[j] and s[i]==char_list[k]:\n",
    "                        dp[k][i][j] = 2\n",
    "                        for m in range(4):\n",
    "                            dp[k][i][j] += dp[m][i+1][j-1]\n",
    "                    elif s[i]==char_list[k] and s[i] != s[j]:\n",
    "                        dp[k][i][j] = dp[k][i][j-1]\n",
    "                    elif s[j]==char_list[k] and s[i]!= s[j]:\n",
    "                        dp[k][i][j] = dp[k][i+1][j]\n",
    "                    else:\n",
    "                        dp[k][i][j] = dp[k][i+1][j-1]\n",
    "        ans = 0\n",
    "        for k in range(4):\n",
    "            ans += dp[k][0][n-1]\n",
    "        return ans % 1000000007\n",
    "                        \n",
    "                            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequences(self, s: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(s)\n",
    "        # State dp (x, i, j) represents the total number of different\n",
    "        # palindrome sequences starting and ending with the character x \n",
    "        # in the string interval s [i: j], where s [i: j] represents the\n",
    "        # substring of from i to j (include i, j).\n",
    "        # Thus the result is sum(dp(x , 0, n-1)), which x in (a, b, c, d) \n",
    "        dp = [[[1 if i==j and s[i] == chr(ord('a')+c) else 0 for i in range(n)] for j in range(n)] for c in range(4)]\n",
    "\n",
    "\n",
    "        for j in range(1, n):\n",
    "            for i in range(j-1, -1, -1):\n",
    "                for k, c in enumerate(\"abcd\"):\n",
    "                    if s[i] == s[j] == c:\n",
    "                        dp[k][i][j] = (dp[0][i+1][j-1] + dp[1][i+1][j-1] + dp[2][i+1][j-1] + dp[3][i+1][j-1] + 2) % MOD\n",
    "                    elif s[i] == c:\n",
    "                        dp[k][i][j] = dp[k][i][j-1]\n",
    "                    elif s[j] == c:\n",
    "                        dp[k][i][j] = dp[k][i+1][j]\n",
    "                    else:\n",
    "                        dp[k][i][j] = dp[k][i+1][j-1]\n",
    "        \n",
    "        return (dp[0][0][n-1] + dp[1][0][n-1] + dp[2][0][n-1] + dp[3][0][n-1]) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequences(self, s: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(s)\n",
    "        f = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(4)]\n",
    "        for i, x in enumerate(s):\n",
    "            f[ord(x) - ord('a')][i][i] = 1\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(i+1, n):\n",
    "                for k, c in enumerate('abcd'):\n",
    "                    if s[i] == s[j] == c:\n",
    "                        f[k][i][j] = (2 + sum(ff[i+1][j-1] for ff in f)) % MOD\n",
    "                    elif s[i] == c:\n",
    "                        f[k][i][j] = f[k][i][j-1]\n",
    "                    elif s[j] == c:\n",
    "                        f[k][i][j] = f[k][i+1][j]\n",
    "                    else:\n",
    "                        f[k][i][j] = f[k][i+1][j-1]\n",
    "        return sum(ff[0][n-1] for ff in f) % MOD\n",
    "                        \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequences(self, s):\n",
    "        \"\"\"\n",
    "        统计字符串中的不同回文子序列\n",
    "        Args:\n",
    "            s (str): \n",
    "        returns (int):\n",
    "        \"\"\"\n",
    "        #处理异常情况\n",
    "        if s == None or len(s) == 0:\n",
    "            return 0 \n",
    "        n = len(s)\n",
    "        if n == 1:\n",
    "            return 1 \n",
    "        MOD = 1e9 + 7\n",
    "        \n",
    "        #由于只存在 'a', 'b', 'c', 'd'四种字母, k = 0,1,2,3 对于分别对应'a', 'b', 'c', 'd'\n",
    "        #dp的定义, dp[k][i][j]表示 在s[i....j]的子字符串中, 以x字母为开头or结尾的回文子串的不同的回文子串个数\n",
    "        dp = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(4)]\n",
    "    \n",
    "        #dp的初始化\n",
    "        for i in range(n):\n",
    "            k = ord(s[i]) - ord('a')\n",
    "            dp[k][i][i] = 1\n",
    "        \n",
    "                \n",
    "        char_list = ['a', 'b', 'c', 'd']\n",
    "        #dp的遍历\n",
    "        for i in range(n-2, -1, -1):\n",
    "            for j in range(i + 1, n):\n",
    "                for k in range(4):\n",
    "                    c = char_list[k]\n",
    "                    #case1. 以x为开头or结尾的回文串, s[i] == s[j] == x, dp[x][i][j] = 2 + dp[0][i+1][j-1] dp[1][i+1][j-1] + dp[2][i+1][j-1] + dp[3][i+1][j-1]\n",
    "                    if s[i] == s[j] == c:\n",
    "                        dp[k][i][j] = (2 + dp[0][i+1][j-1] + dp[1][i+1][j-1] + dp[2][i+1][j-1] + dp[3][i+1][j-1]) % MOD\n",
    "                    \n",
    "                    #case2. s[i] == x, s[j] != x, dp[x][i][j] = dp[x][i][j-1]\n",
    "                    elif s[i] == c and s[j] != c:\n",
    "                        dp[k][i][j] = dp[k][i][j-1]\n",
    "                    \n",
    "                    #case3. s[i] != x, s[j] == x, dp[x][i][j] = dp[x][i + 1][j]\n",
    "                    elif s[i] != c and s[j] == c:\n",
    "                         dp[k][i][j] = dp[k][i + 1][j]\n",
    "                    \n",
    "                    #case4. s[i] != x, s[j] != x, dp[x][i][j] = dp[x][i+1][j-1]\n",
    "                    elif s[i] != c and s[j] != c:\n",
    "                        dp[k][i][j] = dp[k][i+1][j-1]\n",
    "\n",
    "        ans = 0\n",
    "        #return \n",
    "        for i in range(4):\n",
    "            ans += dp[i][0][-1] \n",
    "        \n",
    "        return int(ans % MOD)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequences(self, s: str) -> int:\n",
    "        def lt730(s):\n",
    "            chars='abcd'\n",
    "            c=4\n",
    "            n=len(s)\n",
    "            # dp[x][i][j] 代表字符x开头结尾的，i-j区间的，不同回文子序列的数目\n",
    "            dp=[[[0 for j in range(n)] for i in range(n)] for k in range(c)]\n",
    "\n",
    "            #因为没一个ij区间，都要用到子区间的全部x信息，所以x要放在最内层遍历；\n",
    "            for i in range(n-1,-1,-1):\n",
    "                for j in range(i,n):\n",
    "                    for x in range(c):\n",
    "                        if i==j:\n",
    "                            if s[i]==chars[x]:dp[x][i][j]=1\n",
    "                        elif i<j:\n",
    "                            if s[i]==s[j]==chars[x]:\n",
    "                                dp[x][i][j]=sum([dp[x_][i+1][j-1] for x_ in range(c)  ])+2\n",
    "                            elif s[i]==chars[x]:\n",
    "                                dp[x][i][j]=dp[x][i][j-1]\n",
    "                            elif s[j]==chars[x]:\n",
    "                                dp[x][i][j]=dp[x][i+1][j]\n",
    "                            else:\n",
    "                                dp[x][i][j]=dp[x][i+1][j-1]\n",
    "            return sum([dp[x_][0][n-1] for x_ in range(c)])%(10**9+7)\n",
    "        return lt730(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#统计不同回文子序列,记忆化搜索\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def countPalindromicSubsequences(self, s: str) -> int:\n",
    "        mod=10**9+7\n",
    "        @lru_cache(None)\n",
    "        def dfs(left,right):\n",
    "            if left>=right:return int(left==right)#如果l==r,搜索到单字符，对结果贡献为1\n",
    "            res=0\n",
    "            for ch in'abcd':\n",
    "                l,r=s.find(ch,left,right+1),s.rfind(ch,left,right+1)\n",
    "                if l==-1:continue \n",
    "                if r==l:res+=1\n",
    "                else:res+=dfs(l+1,r-1)+2\n",
    "                res%=mod\n",
    "            return res \n",
    "        return dfs(0,len(s)-1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequences(self, s: str) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(left, right):\n",
    "            if left >= right:\n",
    "                return int(left == right)\n",
    "            res = 0\n",
    "            for ch in \"abcd\":\n",
    "                l, r = s.find(ch, left, right + 1), s.rfind(ch, left, right + 1)\n",
    "                if l == -1:\n",
    "                    continue\n",
    "                if r == l:\n",
    "                    res += 1\n",
    "                else:\n",
    "                    res += dfs(l + 1, r - 1) + 2\n",
    "                res %= mod\n",
    "            return res\n",
    "\n",
    "        return dfs(0, len(s) - 1)\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
